package leetcode.easy;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 1.  问题：给定一个大小为n的正数数组，从这个数组中找到k个数的和等于一个给定数target
 * 计算出有多少种组合方式？
 * 例子：1 2 3 4 5 6 7 8 k=3 target=11
 * 输入数组 [1,2,3,4], k = 2, target = 5
 * 2种解决方案: [1,4] 和 [2,3]
 * 结果： 2
 * @author TANGYE
 * @date 2021/2/24 8:52 下午
 **/
public class One {

    private static int result = 0;
    /**
     * 先把当前遍历的值存下来， 后面直接判断target-nums[i]是否存在即可
     * 不管K是多少，到最后都是求两个数的和
     * @param nums 给定数组
     * @param target 目标和
     * @return
     */
    public static int find(int[] nums, int k, int start, int target){
        if (k == 2){
            Map<Integer, Integer> map = new HashMap();
            for (int i = start; i < nums.length; i++) {
                Integer num = map.get(target - nums[i]);
                if (null != num) {
                    result++;
                }
                map.put(nums[i], i);
            }
        } else {
            for (int i = start; i < nums.length - (k - 1); i++) {
                if (i > start && nums[i] == nums[i - 1]) continue;
                find(nums, k - 1, i + 1, target - nums[i]);
            }
        }

        return result;
    }

    public static int firstDo(int[] nums, int k, int start, int target){
        if (null == nums || nums.length == 1){
            return result;
        }
        Arrays.sort(nums);
        return find(nums,k,start,target);
    }

    public static void main(String[] args){
        int[] nums = new int[]{1,2,3,4,5,6};
        int target = 9;
        int k = 3;
        int result = firstDo(nums, k, 0, target);
        System.out.println(result);
    }
}
